#include <bits/stdc++.h>

#define N 100005

using namespace std;

struct edge{
    int to;
    int val;
};

struct node{
    int dis;
    int id;
    //重载“<”运算符
    bool operator<(const node& other)const{
        return dis > other.dis;
    }
};

vector <edge> G[N];
int dis[N];
int n, m, s;
bool isfind[100000]; //是否最短

void addedge(int fr, int to, int dis){
    G[fr].push_back((edge){to, dis});
}

void dijkstra_heap(int scr){
    priority_queue<node> pq;
    bool find[N] = {false};
    dis[scr] = 0;
    pq.push((node){0, scr}); //dis, id

    while(!pq.empty()){
        node u = pq.top();  pq.pop();
        if(u.dis > dis[u.id])   continue;
        for(edge& e : G[u.id]){
            if (dis[e.to] > dis[u.id] + e.val) {
                dis[e.to] = dis[u.id] + e.val;
                pq.push((node){dis[e.to], e.to});
            }
        }
    }
}
int main(){
    //freopen("E:/CodeLearning/ProblemData/P4779_1.in", "r", stdin);
    cin >> n >> m >> s;
    fill(dis, dis + n + 1, 0x7fffffff);
    int u, v, val;
    for(int i = 1; i <= m; i++){
        scanf("%d %d %d", &u, &v, &val);
        addedge(u, v, val);
    }
    dijkstra_heap(s);
    for(int i = 1; i <= n; i++){
        printf("%d ", dis[i]);
    }
    cout << "\n";
    return 0;
}